#include <iostream>
struct ListNode {
    int val;       
    ListNode* next;   
    ListNode(int value) : val(value), next(nullptr) {}
};
ListNode* partition(ListNode* head, int pivot) {
    ListNode* smallerHead = nullptr;
    ListNode* smallerTail = nullptr;
    ListNode* greaterHead = nullptr;
    ListNode* greaterTail = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextNode = curr->next;
        curr->next = nullptr;
        if (curr->val < pivot) {
            if (smallerHead == nullptr) {
                smallerHead = curr;
                smallerTail = curr;
            } else {
                smallerTail->next = curr;
                smallerTail = curr;
            }
        } else {
            if (greaterHead == nullptr) {
                greaterHead = curr;
                greaterTail = curr;
            } else {
                greaterTail->next = curr;
                greaterTail = curr;
            }
        }
        curr = nextNode;
    }
    if (smallerHead == nullptr) {
        return greaterHead;
    }
    smallerTail->next = greaterHead;
    return smallerHead;
}
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " -> ";
        curr = curr->next;
    }
    std::cout << "nullptr" << std::endl;
}
int main() {
    ListNode* head = new ListNode(3);
    ListNode* node1 = new ListNode(5);
    ListNode* node2 = new ListNode(8);
    ListNode* node3 = new ListNode(2);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(1);
    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    std::cout << "Initial List: ";
    printList(head);
    int pivot = 4;
    ListNode* newHead = partition(head, pivot);
    std::cout << "Partitioned List: ";
    printList(newHead);
    ListNode* curr = newHead;
    while (curr != nullptr) {
        ListNode* nextNode = curr->next;
        delete curr;
        curr = nextNode;
    }
    return 0;
}